package leetcode_top;
import java.util.*;
import org.junit.*;
public class Ex227 {

    class Solution {
        //用套路解题
        Map<Character, Integer> map = new HashMap<>();
        public int calculate(String s) {

            //1.构造优先级字典
            map.put('+', 1);
            map.put('-', 1);
            map.put('*', 2);
            map.put('/', 2);
            map.put('%', 3);
            map.put('^', 3);

            //处理异常字符
            s = s.replaceAll(" ", "");
            s = '0' + s;
            s = s.replaceAll("\\(+", "\\(0+");
            s = s.replaceAll("\\(-", "\\(0-");

            Stack<Long> nums = new Stack<>();
            Stack<Character> ops = new Stack<>();

            char[] cs = s.toCharArray();
            int idx = 0, i;
            long last, a, b;
            char c;
            int cu;

            while (idx < cs.length) {
                c = cs[idx];
                if (isDigit(c)) { //处理数字，乘以10+cur原则
                    i = idx;
                    last = 0;
                    while (i < cs.length && isDigit(cs[i])) {
                        last = last * 10 + cs[i++] - '0';
                    }
                    nums.push(last);
                    idx = i - 1; //在后面统一右移指针
                } else {
                    if (ops.isEmpty()) { //做判空逻辑, 不和后面合并是为了减少判断(or很麻烦)
                        ops.push(c);
                    } else if (c == '(' || (cu = map.get(c)) > map.get(ops.peek())) { 
                        ops.push(c);
                    } else if (c == ')') { //遇到右括号，出栈到(
                        while (ops.peek() != '(') {
                            b = nums.pop();
                            a = nums.pop();
                            nums.push(calc(a, b, ops.pop()));
                        }
                        ops.pop();//左括号出栈
                    } else { //栈顶运算符优先级高于此刻的，将栈中能算的都算了
                        while (!ops.isEmpty() && ops.peek() != '(') {
                            if (cu <= map.get(ops.peek())) {
                                b = nums.pop();
                                a = nums.pop();
                                nums.push(calc(a, b, ops.pop()));
                            } else break;
                        }
                        ops.push(c);//记得将当前字符给放进去
                    } 
                }
                idx++;
            }
            //将ops消耗完
            while (!ops.isEmpty()) {
                b = nums.pop();
                a = nums.pop();
                nums.push(calc(a, b, ops.pop()));
            }
            return (int)(nums.peek().longValue());
        }

        public long calc(long a, long b, char c) {
            switch (c) {
                case '+':
                    return a + b;
                case '-':
                    return a - b;
                case '*':
                    return a * b;
                case '/':
                    return a / b;
                case '%':
                    return a % b;
                case '^':
                    return (long)Math.pow(a, b);
                default:
                    System.out.println("还可以再自定义运算符");
            }
            return 0;
        }

        private boolean isDigit(char c) {
            return c >= '0' && c <= '9';
        }
    }

    @Test
    public void test1() {
        Solution s = new Solution();
        System.out.println(s.calculate(" 34151/214*417-14-10*2 "));        
    }
    class Solution1 {
        public int calculate(String s) {
            s = s.replace(" ", "");
            s += '#';
            Stack<Integer> stack = new Stack<>();
            char[] cs = s.toCharArray();
            int last = -1;
            char lastC = '#';
            for (int i = 0; i < cs.length; i++) { //" 34151/214*417-14-10*2 "
                if (isDigit(cs[i])) {
                    if (last < 0) 
                        last = cs[i] - '0';
                    else 
                        last = last * 10 + cs[i] - '0';
                } else {
                    if (last >= 0) {
                        stack.push(last);
                        last = -1;
                    }
                    if (cs[i] == '*' || cs[i] == '/') {
                        //需要立即计算
                        int b = 0;
                        int j = i + 1;
                        for (; j < cs.length; j++) {
                            if (!isDigit(cs[j])) break;
                            b = b * 10 + cs[j] - '0';
                        }
                        if (cs[i] == '*') {
                            b = stack.pop() * b;
                        } else {
                            b = stack.pop() / b;
                        }
                        stack.push(b);
                        i = j - 1;
                    } else {
                        if (lastC != '#') {
                            int b = stack.pop();
                            int a = stack.pop();
                            if (lastC == '+') {
                                stack.push(a + b);
                            } else {
                                stack.push(a - b);
                            }
                        }
                        lastC = cs[i];
                    }
                }
            }
            
            if (stack.size() > 1) {
                if (lastC != '#') {
                    int b = stack.pop();
                    int a = stack.pop();
                    if (lastC == '+') {
                        stack.push(a + b);
                    } else {
                        stack.push(a - b);
                    }
                }
            }
            return stack.peek();
        }

        private boolean isDigit(char c) {
            return c >= '0' && c <= '9';
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.calculate(" 34151/214*417-14-10*2 "));        
    }
}
